package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/6/21 17:35
 * @description：
 */
public class Main {
    private static List<Double> proportions = new ArrayList<>();
    private static Map<Double, List<int[]>> whitelist = new HashMap<>();

    /**
     * 初始化白名单
     */
    private static void init() {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String demo = in.nextLine();
            if ("exit".equals(demo)) break;
            ArrayList<int[]> sizes = new ArrayList<>();  // init
            String[] splits = demo.split("、");
            for (String split : splits) {
                int x = split.indexOf("x");
                int w = Integer.parseInt(split.substring(0, x));
                int h = Integer.parseInt(split.substring(x + 1, split.length()));
                sizes.add(new int[]{w, h});
            }
            if (sizes.size() > 0) {
                double proportion = (double) sizes.get(0)[0] / sizes.get(0)[1];
                whitelist.put(proportion, sizes);
                proportions.add(proportion);
            }
        }
        //System.out.println(proportions);
        /*for(Map.Entry<Double, List<int[]>> entry : whitelist.entrySet()) {
            List<int[]> values = entry.getValue();
            System.out.println(entry.getKey());
            for (int[] value : values) {
                System.out.print(Arrays.toString(value));
            }
            System.out.println();
        }*/
    }

    public static void main(String[] args) {
        init();
        add(750, 560);
        //自测
        testOwn();

        //testAll();
        /*Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        for (int i = 0; i < N; i++) {
            int w = in.nextInt();
            int h = in.nextInt();
            int[] ans= searchClosest(w, h);
            System.out.println("[" + w + ", " + h + "]" + " 命中后：" +"[" + ans[0] + ", " + ans[1] + "]" );
        }*/
    }

    private static void add(int w, int h) {
        double rate = (double) w / h;
        List<int[]> list = whitelist.getOrDefault(rate, new ArrayList<int[]>());
        if (!whitelist.containsKey(rate)) {
            proportions.add(rate);
        }
        list.add(new int[]{w, h});
        whitelist.put(rate, list);
    }

    /**
     * 单测
     */
    public static void testOwn() {
        Scanner in = new Scanner(System.in);
        int w = in.nextInt();
        int h = in.nextInt();
        int[] ans = searchClosest(w, h);
        System.out.println(Arrays.toString(ans));
    }

    /**
     * 测试全部数据
     */
    public static void testAll() {
        //大数据测试
        int res = 0;
        int count = 0;
        int maxDiff = Integer.MIN_VALUE;
        long startTime = System.currentTimeMillis();
        for (int i = 100; i <= 750; i++) {
            for (int j = 100; j <= 480; j++) {
                if ((double)(i / j) <= proportions.get(proportions.size() - 1) && (double)(i / j) >= proportions.get(0)) {
                    int w = i;
                    int h = j;
                    int[] ans = searchClosest(w, h);
                    int diff = ans[0] * ans[1] - w * h;
                    res += diff;
                    maxDiff = Math.max(maxDiff, diff);

                    count++;
                    System.out.println("[" + w + ", " + h + "]" + "\t" + Arrays.toString(ans));
                    /*if (diff == 22000) {
                        return;
                    }*/
                }
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("总共耗时:" + (endTime - startTime) + "ms");
        System.out.println("最大像素差：" + maxDiff);
        //System.out.println("最大像素差元素：" + "[100, 100]  [200, 160]");
        System.out.println("平均像素差：" + (double) res / count);
    }

    private static int[] searchClosest(int w, int h) {
        double proportion = (double) w / h;
        if (proportions.size() <= 0) {
            throw new RuntimeException("未初始化白名单");
        }
        proportions.sort(Double :: compare);
        if (proportion < proportions.get(0) || proportion > proportions.get(proportions.size() - 1)) {
            //throw new RuntimeException("数据不合法");
        }
        int left =  binarySearch(proportion);  //
        //查找出了比例接近的集合
        double[] doubles = new double[3];
        Arrays.fill(doubles, Double.MAX_VALUE);
        if (left != -1) {
            double[] ans1 = find(whitelist.get(proportions.get(left)), w, h);
            double[] ans2;
            ans2 = left + 1 < whitelist.size() ? find(whitelist.get(proportions.get(left + 1)), w, h) : null;
            if (ans2 != null || ans1 != null) {
                double[] ans = (ans1 == null ? Double.MAX_VALUE : ans1[0])
                        > (ans2 == null ? Double.MAX_VALUE : ans2[0])
                        ? ans2 : ans1;
                doubles[0] = ans[0];
                doubles[1] = ans[1];
                doubles[2] = ans[2];
            }
        }
        if (doubles[0] == Double.MAX_VALUE) {
            for (Double pro : proportions) {
                List<int[]> sizes = whitelist.get(pro);
                double[] curAns = find(sizes, w, h);
                if (curAns == null) continue;
                if (curAns[0] < doubles[0]) {
                    doubles[0] = curAns[0];
                    doubles[1] = curAns[1];
                    doubles[2] = curAns[2];
                }
            }
        }
        if (doubles[0] == Double.MAX_VALUE) {
            return null;
        } else {
            int[] ans = new int[2];
            ans[0] = (int) doubles[1];
            ans[1] = (int) doubles[2];
            return ans;
        }
    }

    /**
     * 寻找指定比例中与目标矩形最接近的矩形像素
     * @param sizes
     * @param w
     * @param h
     * @return
     */
    private static double[] find(List<int[]> sizes, int w, int h) {
        double[] min = new double[3];
        int maxDiff = Integer.MAX_VALUE;
        Arrays.fill(min, Double.MAX_VALUE);
        for (int[] size : sizes) {
            int curW = size[0];
            int curH = size[1];
            if (curW < w || curH < h) continue;
            int areaDiff = Math.abs(curW * curH - w * h);
            //int rate = areaDiff;
            //等于逻辑
            /*if (areaDiff == maxDiff) {

            }*/
            if (areaDiff < maxDiff) {
                double rate = Math.abs((double) curW / (double) curH - w / h);
                maxDiff = areaDiff;
                min[0] = rate;
                min[1] = curW;
                min[2] = curH;
            }
        }
        return min[0] == Double.MAX_VALUE ? null : min;
    }

    /**
     * 查询小于等于proportion的最大值
     * @param proportion
     * @return
     */
    private static int
    binarySearch(double proportion) {
        int l = 0;
        int r = proportions.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (proportions.get(mid) <= proportion) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return proportions.get(r) <= proportion ? r : -1;
    }
}
